#include <string>
using namespace std;
class Solution
{
public:
    string remove(const string &s)
    {
        string t;
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] != '*')
            {
                t += s[i];
            }
            else
            {
                if (t.size() == 0 || s.back() != '*')
                {
                    t += s[i];
                }
            }
        }
        return t;
    }
    int isMatch2(string s, string p)
    {
        const int s_len = s.size();
        const int p_len = p.size();
        if (s_len == 0 && p_len == 0)
        {
            return 1;
        }
        if (s_len == 0 && p_len)
        {
            for (int i = 0; i < p_len; i++)
            {
                if (p[i] != '*')
                {
                    return -1;
                }
            }
        }
        if (s_len && p_len == 0)
        {
            return -1;
        }
        if (p_len == 1 && p[0] == '*')
        {
            return 1;
        }
        int i;
        for (i = 0; i < min(s_len, p_len); i++)
        {
            if (s[i] != p[i] && p[i] != '?')
            {
                break;
            }
        }
        if (i)
        {
            return isMatch2(s.substr(i), p.substr(i));
        }
        if (p[0] != '*')
        {
            return -1;
        }
        string p_rest = p.substr(1);
        string prp = p_rest.substr(1);
        int r;
        for (int i = 0; i < s_len; i++)
        {
            if(s[i]!=p_rest[0]&&p_rest[0]!='?'){
                continue;
            }
            string ss = s.substr(i+1);
            if((r=isMatch2(ss,prp))!=-1)
            {
                return r;
            }
        }
        return 1;
    }
    bool isMatch(string s, string p)
    {
        string pp = remove(p);
        return isMatch2(s, pp) == 1;
    }
};